package lanQiaoBei.搜索与图论.最小生成树;
import java.io.*;
import java.math.*;
import java.util.*;
/*prim算法适用于稠密图求最小生成树(n^2)
*题目链接 https://blog.csdn.net/qq_45260619/article/details/115479209
4 5
1 2 1
1 3 2
1 4 3
2 3 2
3 4 4

6
* */
public class P1 {
       static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
       static final int N=510;
       static int g[][]=new int[N][N],d[]=new int[N],n,m;
       static boolean close[]=new boolean[N];
       static int prim(){
              Arrays.fill(d,Integer.MAX_VALUE);
              int res=0;
              for(int i=0;i<n;i++){
                     int t=-1;
                     for(int j=1;j<=n;j++)//找到本次循环需要拓展的点即距离最小点
                            if(!close[j]&&(t==-1||d[j]<d[t]))
                                   t=j;
                     close[t]=true;//将该点锁住 不再遍历它
                     if(i!=0&&d[t]==Integer.MAX_VALUE)return -1;//如果不是起始点且没有找到最短相邻点 说明图不连通不存在最小生成树
                     if(i!=0)res+=d[t];
                     for(int j=1;j<=n;j++)
                            d[j]=Math.min(d[j],g[t][j]);
              }
              return res;
       }
       public static void main(String[] ss) throws IOException {
              ss=br.readLine().split(" ");
              n=Integer.parseInt(ss[0]);m=Integer.parseInt(ss[1]);
              for(int i=1;i<=n;i++)//将各个点的初始距离初始化为正无穷
                     Arrays.fill(g[i],Integer.MAX_VALUE);

              while(m-->0){
                     ss=br.readLine().split(" ");
                     int a=Integer.parseInt(ss[0]),b=Integer.parseInt(ss[1]),w=Integer.parseInt(ss[2]);
                     if(a!=b){//去掉自环
                            g[a][b]=Math.min(g[a][b],w);//取最小的重边
                     }
              }
              System.out.println(prim());
       }
}
